import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/6 18:54
 * @description 动态规划
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        // 定义 dp[i][j]为 合并arr[i..j]之间的数的最小乘积和, 那么答案为dp[0][n-1]
        // 确定转移方程：dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + maxVal[i][k] * maxVal[k + 1][j]
        // maxVal[i][j]代表区间[i..j]之间的最大元素
        int[][] dp = new int[n][n];
        int[][] maxVal = new int[n][n];
        for (int i = 0; i < n; i++) {
            maxVal[i][i] = arr[i];
            for (int j = i + 1; j < n; j++) {
                maxVal[i][j] = Math.max(maxVal[i][j - 1], arr[j]);
            }
        }
        for(int len = 1; len < n; len++) {
            for(int i = 0; i + len < n; i++) {
                dp[i][i+len] = Integer.MAX_VALUE;
                for(int k = i; k < i + len; k++) {
                    dp[i][i+len] = Math.min(dp[i][i+len], dp[i][k] + dp[k+1][i+len] + maxVal[i][k] * maxVal[k+1][i+len]);
                }
            }
        }
        return dp[0][n -1];
    }
}
